package main

import (
	"fmt"
)

/**
Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

Example:

Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4

	合并两个有序链表，并返回合并后的新链表

分析:
采用递归

![20171220151377563646517.png](http://cdn.bsummer.cn/20171220151377563646517.png)
![20171220151377677047598.png](http://cdn.bsummer.cn/20171220151377677047598.png)
*/

type ListNode struct {
	Val  int
	Next *ListNode
}

func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
	if l1 == nil {
		return l2
	}

	if l2 == nil {
		return l1
	}

	head := &ListNode{}

	if l1.Val < l2.Val {
		head.Val = l1.Val
		head.Next = mergeTwoLists(l1.Next, l2)
	} else {
		head.Val = l2.Val
		head.Next = mergeTwoLists(l1, l2.Next)
	}

	return head
}

func main() {
	fmt.Println("请输入链表1，以-1结束")
	l1 := generateList()
	fmt.Println("请输入链表2，以-1结束")
	l2 := generateList()
	res := mergeTwoLists(l1, l2)

	fmt.Println("遍历合并后链表数据为:")
	for res != nil {
		fmt.Println(res.Val)
		res = res.Next
	}
}

/*
*
创建链表 输入-1终止
*/
func generateList() *ListNode {
	var head *ListNode = nil
	var number int
	fmt.Scanln(&number)
	for number != -1 {
		var p *ListNode = &ListNode{} // 指针指向的位置需要初始化分配空间 C中就是malloc
		p.Val = number
		p.Next = nil
		if head != nil {
			var last *ListNode = head
			for last.Next != nil {
				last = last.Next
			}
			last.Next = p
		} else {
			head = p
		}

		fmt.Scanln(&number)
	}

	return head
}

/**
 */
func generateListByVals(nums []int) *ListNode {
	var head *ListNode = nil
	for _, number := range nums {
		var p *ListNode = &ListNode{} // 指针指向的位置需要初始化分配空间 C中就是malloc
		p.Val = number
		p.Next = nil
		if head != nil {
			var last *ListNode = head
			for last.Next != nil {
				last = last.Next
			}
			last.Next = p
		} else {
			head = p
		}

		fmt.Scanln(&number)
	}

	return head
}
